Complexity Theory I

July, 2021
complexity-theory theory-cs

First part of the course topics are here.

Second part of the course invloving advanced topics like PSPACE, Space bounded computations, Polynomial Hierarchy, Arithmetic Circuits, Boolean Function Analysis etc will be taught by Nitin Saurabh during Oct - Nov. See https://nitinsau.github.io/CT-m21-iiith.html

Prerequisites

Assumes basic knowledge of Discrete Maths, Linear Algebra, Probability, and Algorithms. Highly recomended to brush up these concepts. Some references are given bellow:

Schedule

Meetings

From 15th August - 30th September, 2021

  • Live Lectures: Tuesday, Friday (5:00 pm - 6:30 pm)
  • Tutorials: Saturday (2:30 pm -4:00 pm)
  • Office Hours: Wednesday, 3-430PM. I will be available on Teams during the timings given bellow, for clearing any doubts. You can sent a direct message to me for joining.

Expected Workload

Students are expected to spent atleast 12 hrs per week. Roughly

  • 3+1 hrs attending lectures and tutorials
  • 4 hrs reading textbooks, references etc
  • 4 hrs solving assignments, quizes etc

Evaluations

  • 4 Light Quizzes (Wieghtage: 30%, Best 3 of 4). 20 min MCQ Test to check your understanding of definitions and to ensure that you have gone through reading material.
    • 28 August and 4, 18, 25 September.
  • 3 Assignments (Wieghtage: 30%, ^Best 5 of 6). Problems will require longer to solve. You will need to upload written solutions. One of the assignments which will be harder can be assigned to a group of students. Groups will be formed by the instructors.
    Dates for Release | Submission | Marks Release given bellow:
    1. 20 Aug | 30 Aug | 10 Sept
    2. 30 Aug | 10 Sept | 20 Sept
    3. 10 Aug | 20 Sept | 30 Sept (Group Assignment)
      ^There will be 3 more assignments in the Part II.
  • 2 Deep Quizzes (Wieghtage: 30%, ^Best 3 of 4). We will be doing timed exams of 1hr in moodle.
    1. Between 6-8 Sept | Mark release by 18th Sept.
    2. 30th Sept | Marks release by 10th Oct.
      ^There will be 2 more in the Part II.
  • Scribe Notes or Presentations (Wieghtage: 10%). Students will be given a choice to scribe notes for a lecture or do presentations on an advanced topic. They will be evaluated on clarity of explaining the concepts. Some of the topics for presentation are listed bellow:
    1. PAC Learning and Sample Complexity
    2. Property Testing
    3. One Way functions in Cryptography
    4. Communication Complexity

Lectures

1. Computational Models, Encoding of Problems

1.1 Motivations

1.2 Representations, Prefix Free Encoding, Turing Machine Model, Encoding TMs

1.3 Decidability, Universal TMs, Halting Problem, R/RE Languages, Robustness of TMs

2. Complexity Measures and Classes

2.1 Complexity Measure and Classes, Non determinism, P, NP

2.2 Circuits, Shannon’s Lowerbound

3. Reductions and Completeness

3.1 P, NP, Verifier definition, Reduction

3.2 Cook, Levin Theorem

  • Notes
  • Read:
    • Slides Slides by Prof. Ryan Williams.
    • Lec 5 Slides from Prof. Nabil.

3.3 Cook-Levin Theorem, More Reductions

3.4 CoNP, CoNP Complete, Reachability in small space

3.5 Savitch’s Theorem, L, NL, NL-Completeness, Log-Space Reductions

Textbook and References

As Taught Elsewhere